package org.example.dynamic_planning;

import java.util.Arrays;

public class The_best_time_to_buy_and_sell_stocks_III {
    public static void main(String[] args) {
        //买卖股票的最佳时机 III

        //给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
        //设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
        //注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
        int[] prices = {3,3,5,0,0,3,1,4};
        int i = maxProfit(prices);
        System.out.println(i);
    }

    public static int maxProfit(int[] prices) {
        int[] dp = new int[4];
        dp[0] = -prices[0];
        dp[2] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[0] = Math.max(dp[0],-prices[i]);
            dp[1] = Math.max(dp[1],dp[0] + prices[i]);
            dp[2] = Math.max(dp[2],dp[1] - prices[i]);
            dp[3] = Math.max(dp[3],dp[2] + prices[i]);
        }
        return dp[3];
    }
    //二维数组
    public static int maxProfit2(int[] prices) {
        int[][] dp = new int[prices.length][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3] + prices[i]);
        }
        return dp[prices.length-1][4];
    }
    //超时
    public static int maxProfit3(int[] prices) {
        int sum1 = 0;
        int sum2 = 0;
        int money = 0;
        for (int i = 0; i < prices.length; i++) {
            if (i>=2) sum1 = getMaxMoney(0,i-1,prices);
            if (i<prices.length-1) sum2 = getMaxMoney(i,prices.length-1,prices);
            money = Math.max(money,sum1+sum2);
        }
        return money;
    }
    public static int getMaxMoney(int begin,int end,int[] prices){
        int money = 0;
        int buy = Integer.MAX_VALUE;
        for (int i = begin; i <= end; i++) {
            if (prices[i] >= buy){
                money = Math.max(money,prices[i] - buy);
            }else {
                buy = prices[i];
            }
        }
        return money;
    }
}
